/*
 * SplitVec.h
 *
 *  Created on: 2012-9-5
 *      Author: yangentao@gmail.com
 */

#ifndef SPLITVEC_H_
#define SPLITVEC_H_

#include "baseutil.h"
#include <boost/scoped_array.hpp>

#define SPLIT_VEC_MIN_CAP	8

template<typename T>
class SplitVec {
protected:
	boost::scoped_array<T> sarray;
	size_t capcity;

	size_t gapPos;
	size_t gapLen;

public:
	SplitVec()
			: capcity(0), gapPos(0), gapLen(0) {
		ensureCapcity(SPLIT_VEC_MIN_CAP);
	}
	SplitVec(size_t capcity_)
			: capcity(0), gapPos(0), gapLen(0) {
		ensureCapcity(Max(SPLIT_VEC_MIN_CAP, capcity_));
	}
	SplitVec(const SplitVec<T>& other)
			: capcity(0), gapPos(0), gapLen(0) {
		copyFrom(other);
	}
	virtual ~SplitVec() {
	}
protected:
	size_t allocSize(size_t increase) const {
		size_t smallest = length() + increase;
		if (smallest > 512) {
			return smallest + 512;
		} else {
			return smallest * 2;
		}
	}

	void gapTo(size_t index, size_t increase = 0) {
		assert(index <= length());
		int delta = index - gapPos;
		if (sarray && gapLen >= increase) {
			if (delta == 0) {
				; //nothing
			} else if (delta > 0) {
				ArrayMove(part1Buffer() + part1Len(), part2Buffer(), delta);
			} else { //delta <0
				ArrayMove(part2Buffer() + delta, part1Buffer() + part1Len() + delta, -delta);
			}
		} else {
			size_t newCap = allocSize(increase);
			T* buf = new T[newCap];
			if (sarray) {
				if (delta == 0) {
					ArrayMove(buf, part1Buffer(), part1Len());
					ArrayMove(buf + newCap - part2Len(), part2Buffer(), part2Len());
				} else if (delta > 0) {
					ArrayMove(buf, part1Buffer(), part1Len());
					ArrayMove(buf + part1Len(), part2Buffer(), delta);
					ArrayMove(buf + newCap - (part2Len() - delta), part2Buffer() + delta, part2Len() - delta);
				} else { //delta < 0
					ArrayMove(buf, part1Buffer(), part1Len() + delta);
					ArrayMove(buf + newCap - part2Len() + delta, part1Buffer() + part1Len() + delta, -delta);
					ArrayMove(buf + newCap - part2Len(), part2Buffer(), part2Len());
				}
			}
			gapLen += newCap - capcity;
			capcity = newCap;
			sarray.reset(buf);
		}
		gapPos = index;
	}
	inline size_t innerIndex(size_t index) const {
		return index >= gapPos ? index + gapLen : index;
	}
	inline size_t part1Len() const {
		return gapPos;
	}
	inline size_t part2Len() const {
		return capcity - gapPos - gapLen;
	}
	inline size_t part1Index() const {
		return 0;
	}
	inline size_t part2Index() const {
		return gapPos + gapLen;
	}
	inline T* part1Buffer() const {
		return sarray.get();
	}
	inline T* part2Buffer() const {
		return sarray.get() + part2Index();
	}
public:
	SplitVec<T> operator=(const SplitVec<T>& other) {
		copyFrom(other);
		return *this;
	}
	void copyFrom(const SplitVec<T>& other) {
		if (capcity < other.length()) {
			capcity = other.length();
			gapPos = capcity;
			gapLen = 0;
			sarray.reset(new T[capcity]);
			ArrayMove(sarray.get(), 0, other.sarray.get(), other.part1Index(), other.part1Len());
			ArrayMove(sarray.get(), other.part1Len(), other.sarray.get(), other.part2Index(), other.part2Len());
		} else {
			ArrayMove(sarray.get(), 0, other.sarray.get(), other.part1Index(), other.part1Len());
			ArrayMove(sarray.get(), other.part1Len(), other.sarray.get(), other.part2Index(), other.part2Len());
			gapPos = other.length();
			gapLen = capcity - other.length();
		}
	}

	inline T* getBuffer() {
		gapTo(length());
		return sarray.get();
	}
	void ensureCapcity(size_t capcity_) {
		if (capcity < capcity_) {
			capcity_ = max(capcity_, 8);
			T* buf = new T[capcity_];
			if (sarray) {
				ArrayMove(buf, 0, sarray.get(), part1Index(), part1Len());
				ArrayMove(buf, part1Len(), sarray.get(), part2Index(), part2Len());
			}
			size_t len = length();
			gapPos = len;
			gapLen = capcity_ - len;
			capcity = capcity_;
			sarray.reset(buf);
		}
	}
	inline size_t getCapcity() {
		return capcity;
	}
	inline size_t length() const {
		return capcity - gapLen;
	}
	inline T get(size_t index) const {
		assert(index < length());
		size_t n = innerIndex(index);
		return sarray[n];

	}
	T& getRef(size_t index) const {
		assert(index < length());
		size_t n = innerIndex(index);
		return sarray[n];

	}
	inline T operator[](int index) const {
		assert(index >=0 && index < length());
		return get(index);
	}
	T& operator[](int index) {
		assert(index >=0 && index < length());
		return getRef(index);
	}
	inline void set(size_t index, const T& value) {
		assert(index < length());
		size_t n = innerIndex(index);
		sarray[n] = value;
	}
	inline T first() const {
		assert(length() > 0);
		return get(0);
	}
	inline T last() const {
		assert(length() > 0);
		return get(length() - 1);
	}
	inline void append(const T& val) {
		replace(length(), 0, &val, 1);
	}
	inline void append(const T* values, size_t count) {
		replace(length(), 0, values, count);
	}
	inline void insert(size_t index, const T& val) {
		replace(index, 0, &val, 1);
	}
	inline void insert(size_t index, const T* values, size_t count) {
		replace(index, 0, values, count);
	}
	inline void remove(size_t index) {
		replace(index, 1, 0, 0);
	}
	inline void remove(size_t index, size_t len) {
		replace(index, len, 0, 0);
	}

	void replace(size_t from, size_t len, const T* arr, size_t arrLen) {
			if (!len && !arrLen) {
				return;
			}
			assert(from + len <= length());
			int lenDelta = arrLen - len;
			gapTo(from, max(0, lenDelta));
			ArrayMove(sarray.get(), from, arr, 0, arrLen);
			gapPos =from + arrLen;
			gapLen -= lenDelta;
		}
	inline void getRange(T* buf, size_t from, size_t len) const {
		if (len) {
			assert(from + len <= length());
			for (int i = 0; i < len; ++i) {
				buf[i] = get(i + from);
			}
		}
	}

	bool equals(const SplitVec& other) {
		size_t len = other.length();
		if (length() == len) {
			if (len) {
				for (size_t i = 0; i < len; ++i) {
					if (get(i) != other[i]) {
						return false;
					}
				}
				return true;
			} else {
				return true;
			}
		}
		return false;
	}
	bool equals(const T* other, size_t len) {
		if (length() == len) {
			if (len) {
				if (other) {
					for (size_t i = 0; i < len; ++i) {
						if (get(i) != other[i]) {
							return false;
						}
					}
					return true;
				} else {
					return false;
				}
			} else {
				return true;
			}
		}
		return false;
	}

public:
	void dump(const char* prefix = 0) {
		if (prefix) {
			cout << prefix;
		}
		cout << "Capcity: " << capcity << "\tGapPos: " << gapPos << "\tGapLen:" << gapLen << endl;
		cout << "[";
		for (int i = 0; i < capcity; ++i) {
			if (i >= gapPos && i < gapPos + gapLen) {
				if (i == gapPos) {
					cout << "[* ";
				} else if (i == gapPos + gapLen - 1) {
					cout << "*] ";
				} else {
					cout << "* ";
				}
			} else {
				cout << get(i >= gapPos ? i - gapLen : i) << " ";
			}
		}
		cout << "]";
		cout << endl;
	}
};

#endif /* SPLITVEC_H_ */
